/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package firstround2009;

import java.util.Map;
import java.util.Queue;
import java.util.HashMap;
import java.util.HashSet;
import java.io.IOException;
import java.util.LinkedList;
import static chanlib.Chan_IO.*;

/**
 * @author robit
 */
public class MultiBaseHappy{
    /*
      All neccesary to be defined
      including:
      variable, inner class
    */
    // static int A;
    // static void B();
    // static class C

    static boolean happy(int base,int x){
        while(x>1000)x=square(x, base);
        return happy[base][x];
    }

    static int square(int x,int base){
         int sum=0;
         while(x>0){
                sum+=(x%base)*(x%base);
                x/=base;
         }
         return sum;
    }

    /*
       One calculation fits all of the cases.
    */
    static boolean known[][];
    static boolean happy[][];
    static int square[][];
    static void preReckon(){
        happy=new boolean[11][1001];
        known=new boolean[11][1001];
        
        HashSet<Integer> rep=new HashSet<Integer>();
        for(int b=2;b<=10;b++){
            for(int x=1;x<1000;x++){
                if(known[b][x])continue;
                rep.clear();
                int itr=x;
                while(rep.add(itr)){
                    itr=square(itr, b);
                }
                boolean ans=itr==1;
                itr=x;
                rep.clear();
                while(rep.add(itr)){
                    happy[b][itr]=ans;
                    known[b][itr]=true;
                    itr=square(itr, b);
                }
            }
        }
    }
    static Map<Integer,Integer> m;
    public static void preContinue(){
        Queue<Integer> q=new LinkedList<Integer>();
        m=new HashMap<Integer,Integer>();
        final int MAXBASE=10;
        int init= 0;
        m.put(init, 2);
        q.add(init);
        while(!q.isEmpty()){
            int e=q.poll();
            int smallest=m.get(e);
            boolean all;
            while(true){
                all=true;
                for(int b=2;b<=MAXBASE;b++){
                    if((e>>b&1)==0)continue;
                    all&=happy(b,smallest);
                }
                if(all)break;
                smallest++;
            }
            m.put(e, smallest);
            for(int b=2;b<=MAXBASE;b++){
                int ne=1<<b|e;
                if(ne==e)continue;
                if(!m.keySet().contains(ne)){
                    m.put(ne, smallest);
                    q.add(ne);
                }else{
                    if(smallest>m.get(ne)) m.put(ne, smallest);
                }
            }
        }


        //for(int k:m.keySet()){
        //    System.out.println(Integer.toBinaryString(k));
        //}
        //System.out.println(m.keySet().size());
        //System.out.println(m);
    }
//        for(int i=1;i<=1000;i++){
//            String c=String.format("at %d is %b %b",i,testBelowThoudson(i, 3),happy[3][i]);
//            System.out.println(c);
//        }



    /*
      calculate the answer
    */
    private static void reckon(int line) {
        String raw=Line();
        String str[]=raw.split(" ");
        int bases[]=new int[str.length];
        int key=0;
        for(int i=0;i<bases.length;i++){
            key|=1<<Integer.parseInt(str[i]);
        }
        //if(t==MAX)System.exit(-1);
        //System.out.println(m.keySet().contains(key));
        int ans = m.get(key);

        String output=String.format("Case #%d: %d",line,ans);
        writeln(output, OUTFILE);
        //writeln(String.format("N=%d K=%d\n%s", N, K, ans),ANALFILE);
        //println(output);
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        /*
           Pre-computing for all cases
        */

        // Just in case!
        preReckon();
        println("PASS1");
        preContinue();
        println("PASS2");
        //System.exit(0);
        //while((char)read()!='P');

        /*
          Input-output
        */
        boolean test=false;
        boolean small=false;
        String prob="A";
        String filename;
        if(test) filename="test";
        else{
            if(small) filename=prob+"-small-practice";
            else filename=prob+"-large-practice";
        }
        try {
            /*
               Init IO,plus determination of input line number
             */
            initIO(filename);
            int lineNums = Integer.parseInt(Line());
            for (int i = 1; i <= lineNums; i++) {
                reckon(i);
            }
        } finally {
            endIO();
        }
    }

}
